#include "../comm.h"
class Solution {
public:


    using PII = pair<int, int>;
    vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
        int n = edges.size() + 1;
        vector<vector<PII>> mp(edges.size() + 1);
        for (auto& v : edges)
        {
            int a = v[0], b = v[1], c = v[2];
            mp[a].push_back({ b, c });
            mp[b].push_back({ a, c });
        }
        function<int(int, int, int)> dfs = [&](int u, int father, int cost) {
            int cnt = 0;
            if (cost % signalSpeed == 0) ++cnt;
            for (auto& [k, w] : mp[u])
            {
                if (k == father) continue;
                cnt += dfs(k, u, (cost + w) % signalSpeed);
            }
            return cnt;
            };
        vector<int> res(n);
        for (int i = 0; i < n; ++i)
        {
            // 左边和根整除，右边也和根整除即可
            auto& v = mp[i];
            int pre = 0;
            for (auto& [k, w] : v)
            {
                // 由于要确保不能往回走，所以需要保存父节点
                int cnt = dfs(k, i, w % signalSpeed);
                res[i] += pre * cnt;
                pre += cnt;
            }

        }
        return res;
    }
};